/*
 * @Description  : 并查集
 * @Autor        : yanwang
 * @CreateDate   : 2021-11-16 16:03:47
 * @LastEditors  : yanwang
 * @LastEditTime : 2021-11-18 14:29:12
 */

/**
 * Quick-Find 算法
 * 
 * 思路：将同一组节点染成相同的颜色
 */
class UnionSet1 {
  constructor(n = 100) {
    this.n = n;
    this.color = new Array(n); // 存放所有节点
    this.init(n);
  }

  // 将各节点颜色定位为自己颜色。
  init(n) {
    for (let i = 0; i < n; i++) {
      this.color[i] = i;
    }
  }

  // 查找x属于哪个集合
  find(x) {
    return this.color[x];
  }

  // 将 b 合并到 a
  merge(a, b) {
    // 此处要保存color[b], 因为下面循环中会改变 color[b] 为 color[a]。
    // 导致b索引后面的元素不会被合并到a。
    const colorB = this.color[b];
    for (let i = 0; i < this.n; i++) {
      if(this.color[i] === colorB) {
        this.color[i] = this.color[a];
      }
    }
  }

  // 判断 a, b 是否属于同一个集合
  query(a, b) {
    return this.find(a) === this.find(b);
  }
}


/**
 * Quick-Union 算法
 * 
 * 思路：将连通关系转换为树形结构，通过递归的方式快速判定。
 */
class UnionSet2 {
  constructor(n = 100) {
    this.n = n;
    // 存放各个节点的父节点
    this.father = new Array(n);
    this.init(n);
  }
  init(n) {
    for (let i = 0; i < n; i++) {
      this.father[i] = i;
    }
  }

  // 查找 x 所属集合（根节点）
  find(x) {
    if(this.father[x] === x) return x;
    return this.find(this.father[x]);

    // return this.father[x] === x ? x : this.find(this.father[x])
  }

  // 将 a 和并到 b
  merge(a, b) {
    const fa = this.find(a); // a的根节点
    const fb = this.find(b); // b的根节点
    if(fa === fb) return; // 已经在一个集合中
    this.father[fa] = fb;
  }

  // 判断 a, b 是否属于同一个集合
  query(a, b) {
    return this.find(a) === this.find(b);
  }
}

/**
 * Weighted-Quick-Union算法
 * 
 * 思路：通过考虑平均查找次数的方式，对合并过程进行优化。
 */
class UnionSet3 {
  constructor(n = 100) {
    this.n = n;
    // 存放各个节点的父节点
    this.father = new Array(n);
    this.size = new Array(n); // 可优化find方法效率
    this.init(n);
  }
  init(n) {
    for (let i = 0; i < n; i++) {
      this.father[i] = i;
      this.size[i] = 1;
    }
  }

  // 查找 x 所属集合（根节点）
  find(x) {
    if(this.father[x] === x) return x;
    return this.find(this.father[x]);

    // return this.father[x] === x ? x : this.find(this.father[x])
  }

  merge(a, b) {
    const fa = this.find(a); // a的根节点
    const fb = this.find(b); // b的根节点
    if(fa === fb) return; // 已经在一个集合中
    if(this.size[fa] < this.size[fb]) { // a集合元素少
      this.father[fa] = fb;  // 将 a 和并到 b
      this.size[fb] += this.size[fa];
    } else {   // 将 b 和并到 a
      this.father[fb] = fa;
      this.size[fa] += this.size[fb];
    }
  }

  // 判断 a, b 是否属于同一个集合
  query(a, b) {
    return this.find(a) === this.find(b);
  }
}

/**
 * 带路径压缩的Weighted-Quick-Union算法
 * 
 * 思路：每次查询连通性关系时，对节点到根节点的路径上所有点进行优化，避免连通性关系从树型结构退 化成链表型结构。
 */

class UnionSet4 {
  constructor(n = 100) {
    this.n = n;
    // 存放各个节点的父节点
    this.father = new Array(n);
    this.size = new Array(n);
    this.init(n);
  }
  init(n) {
    for (let i = 0; i < n; i++) {
      this.father[i] = i;
      this.size[i] = 1;
    }
  }

  // 压缩路径在此过程
  find(x) {
    if(this.father[x] === x) return x;
    let root = this.find(this.father[x]);
    // 将 x 直接挂到根节点
    this.father[x] = root;
    return root;
  }

  merge(a, b) {
    const fa = this.find(a); // a的根节点
    const fb = this.find(b); // b的根节点
    if(fa === fb) return; // 已经在一个集合中
    if(this.size[fa] < this.size[fb]) { // a集合元素少
      this.father[fa] = fb;  // 将 a 和并到 b
      this.size[fb] += this.size[fa];
    } else {   // 将 b 和并到 a
      this.father[fb] = fa;
      this.size[fa] += this.size[fb];
    }
  }

  // 判断 a, b 是否属于同一个集合
  query(a, b) {
    return this.find(a) === this.find(b);
  }
}

/**
 * 带路径压缩的并查集模板
 */
class UnionSet {
  constructor(n = 100) {
    this.father = new Array(n);
    this.init(n);
  }
  init(n) {
    for (let i = 0; i < n; i++) this.father[i] = i;
  }
  
  // 带路径压缩
  find(x) {
    return this.father[x] = (this.father[x] == x ? x : this.find(this.father[x]));
  }
  // 将 a 合并到 b
  merge(a, b) {
    this.father[this.find(a)] = this.find(b);
  }
  query(a, b) {
    return this.find(a) === this.find(b);
  }
}

function test() {
  const unionSet = new UnionSet();
  unionSet.merge(3, 1);
  unionSet.merge(1, 4); 
  console.log(`1属于集合 ${unionSet.find(1)}`);
  console.log(`4属于集合 ${unionSet.find(4)}`);
  console.log(`6属于集合 ${unionSet.find(6)}`);
  console.log(`3、4属于集合一个集合 ${unionSet.query(3, 4)}`);
  console.log(`3、6属于集合一个集合 ${unionSet.query(3, 6)}`);
}
test();